#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size()==0){
            return true;
        }
        //注意，每个值都不重复
        stack<int> S;
        int index = 0;
        
        for(int i = 0;i<pushed.size();++i){
            if(S.empty()||(!S.empty()&&S.top()!=popped[index])){
                S.push(pushed[i]);
            }
            else if(!S.empty()&&S.top()==popped[index]){
                S.pop();
                index++;
                --i;
            }
        }
        while(!S.empty()){
            if(S.top()!=popped[index]){
                return false;
            }
            S.pop();
            ++index;
        }
        return true;
    }
};

int main(){
    Solution S;
    vector<int> pushed = {1,2,3,4,5};
    vector<int> popped = {4,3,5,1,2};
    cout<<S.validateStackSequences(pushed,popped)<<endl;
}